Ce cours s'intéresse au principe de la mémoire virtuelle. Il aborde notamment les notions liées aux défauts de pages.

La multiprogrammation implique de charger plusieurs programmes en mémoire centrale de manière à obtenir un bon taux d'utilisation du processeur. Supposons comme sur la figure 1 ici que l'exécution des programmes 1, 2 et 3 soit nécessaire pour obtenir ce taux d'utilisation du cpu satisfaisant. On peut remarquer qu'une fois les programmes 1 et 2 chargés dans la mémoire, toutes les cases sont occupées : le programme 3 ne peut pas être chargé.

Fig 1 : Cas de figure

Lorsque l'on regarde l'exécution d'un processus, on s'aperçoit qu'à un instant donné le processus n'accède qu'à une partie de son espace d'adressage (par exemple la page de code couramment exécutée par le processeur et la page de données correspondante). Les autres pages de l'espace d'adressage ne sont pas accédées et sont donc inutiles en mémoire centrale. Une solution pour pouvoir charger plus de programmes dans la mémoire centrale est donc de ne charger pour chaque programme que les pages couramment utilisées. Ici par exemple, seules les pages 1,2 et 4 du processus 1 sont chargées ainsi que la page 3 du processus 2 et les pages 1,2,3 du programme 3. Puisque les pages d'un espace d'adressage de processus ne sont pas toutes chargées en mémoire centrale, il faut que le processeur puisse détecter leur éventuelle absence lorsqu'il cherche à effectuer une conversion d'adresse paginée vers l'adresse physique. Chaque entrée de la table des pages com port e alors un champ supplémentaire, le bit Validation V, qui est à vrai (1 ou V) si la page est effectivement présente en mémoire centrale. La figure 2 montre les valeurs des bits de validation pour les tables des pages des trois processus 1, 2 et 3, en tenant compte des chargements de leurs pages en mémoire centrale. Ainsi pour le processus 1, la page 1 est chargée dans la case 2, le bit de validation est à vrai (V). La page 2 est chargée dans la case 4, le bit de validation est à vrai. Par contre la page 3 n'est pas présente en mémoire centrale et donc le bit de validation est à faux (I pour Invalide) : dans ce cas, le champs n° de case n'a pas de signification.

Fig 2 : Bit de validation

Que se passe-t-il à présent lorsque qu'un processus tente d'accéder à une page de son espace d'adressage qui n'est pas en mémoire centrale ? Ici le processus 2 génère une adresse paginée portant sur la page 2. La MMU accède à la table des pages pour effectuer la conversion adresse paginée, adresse physique et teste la valeur du bit de validation : elle le trouve à faux, ce qui veut dire que la page n'est pas chargée dans une case et donc la conversion ne peut être réalisée. Il se produit alors un défaut de page : c'est un déroutement qui oblige le processeur à suspendre l'exécution du programme en cours pour lancer une entrée/sortie qui charge la page manquante en mémoire centrale dans une case libre.

Les figures 3 et 4 illustrent le mécanisme de défaut de page. Le processus cherche à convertir l'adresse logique <p,d>. Il accède donc à l'entrée de sa table des pages correspondant à l'entrée de la page p, et teste la valeur du bit de validation. Celui-ci est à faux (I) indiquant ainsi que la page n'est pas présente. Automatiquement, puisque la traduction vers l'adresse physique ne peut pas être faite, le système lève un défaut de page, qui entraine une entrée/sortie pour charger la page manquante en mémoire centrale. Le défaut de page charge la page manquante dans une case libre de la mémoire centrale, puis le système met à jour l'entrée de la table des pages correspondant à la page p : le bit de validation passe à vrai et le numéro de case physique contenant la page p est renseigné. Enfin, la traduction vers l'adresse physique reprend.

Fig 3 : Mécanisme du défaut de pages

Fig 4 : Mécanisme du défaut de pages

Lors d'un défaut de page, la page manquante est chargée dans une case libre. La totalité des cases de la mémoire centrale peut être occupée : il faut donc libérer une case de la mémoire physique globalement (parmi l'ensemble des cases) ou localement (parmi les cases occupées par les pages du processus en défaut). Le système d'exploitation utilise un algorithme pour choisir une case à libérer. Les deux principaux algorithmes sont :

Avec cet algorithme, c'est la page la plus anciennement chargée qui est remplacée. La figure 5 donne un exemple du fonctionnement de cet algorithme où l'on suppose une mémoire centrale composée de trois cases initialement vides. La lettre D signale l'occurrence de défaut de pages. 

Fig 5 : Remplacement de pages FIFO

Avec cet algorithme, c'est la page la moins récemment accédée qui est remplacée. La figure 6 donne un exemple du fonctionnement de cet algorithme où l'on suppose une mémoire centrale composée de trois cases initialement vides. La lettre D signale l'occurrence de défaut de pages. 

Fig 6 : Remplacement de pages LRU

Finalement, une entrée de la table des pages d'un processus comprendra souvent les champs suivants :

Nous donnons ci-dessous le schéma général de l'algorithme suivi par le système d'exploitation lors de la conversion d'une adresse logique vers une adresse physique. Une daresse est un couple constitué des champs page et déplacement. 

La figure 7 illustre ce phénomène. Elle représente le taux d'utilisation du processeur en fonction du degré de multiprogrammation , c'est-à-dire en fonction du nombre de processus chargés en mémoire centrale. Sur cette figure, on voit clairement que l'utilisation du processeur augmente jusqu'à un certain seuil au delà duquel cette utilisation chute complètement : cette chute correspond à une trop grande activité de pagination des processus qui passent le plus clair de leur temps en entrée/sortie car ils n'ont pas suffisamment de cases mémoires disponibles pour contenir les pages relatives à leur espace de travail courant. 

Fig 7 : Phénomène d'écroulement